package chapter2;

import java.util.Arrays;

public class QuickSort3_1 {
    public static void quickSort(int[] arr,int L,int R){
        if (L<R){
            swap(arr,L+(int)(Math.random()*(R-L+1)),R);
            int[] p =partition(arr,L,R);
            quickSort(arr,L,p[0]-1);
            quickSort(arr,p[1]+1,R);
        }
    }

    public static int[] partition(int[] arr,int L,int R){
        int less = L-1;
        int more = R;
        while (L < more){
            if (arr[L] < arr[R]){
                swap(arr,++less,L++);
            }else if(arr[L] > arr[R]){
                swap(arr,--more,L);
            }else{
                L++;
            }
        }
        swap(arr,more,R);
        return new int[] {less+1,more};
    }

    public static void swap(int[] arr,int x,int y){
        int tmp = arr[x];
        arr[x] =arr[y];
        arr[y] = tmp;
    }

    public static void main(String[] args) {
        int[] arr ={4,2,5,6,8,3,7,9,2,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
